home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 …ember: Reference Library / Dev.CD Dec 00 RL Disk 1.toast / pc / technical documentation / develop / develop issue 27 / develop issue 27 code / shapewalker gx / pathwalking.c next >
Encoding:
C/C++ Source or Header  |  1996-09-28  |  15.9 KB  |  515 lines
  1. /**************************************************************
  2.  
  3.     File:    PathWalking.c
  4.     
  5.  
  6.     Copyright ©, 1996, Apple Computer Inc.
  7.             Daniel I. Lipton
  8.  
  9.     This file contains routines necessary to implement the shape
  10.     walking library.  This library can be used for traversing of 
  11.     line and curve segments in shapes.  The library is callback 
  12.     driven.  Waling a shape will result in callbacks for each segment.
  13.     
  14.         Moveto callback:            changes the current point, called at start of new contour.
  15.         Lineto callback:            a line segment from current point to the specified point.
  16.         Curveto callback:            a curve segment, specified by the 3 points.  The 1st of the three
  17.                                                             will be the current point, but all three are passed anyway.
  18.         Closepath callback:        Called for each contour of a closed shape. (gxCloseFrameFill)
  19.         
  20.         each callback gets the refcon passed into the ShapeWalker call.
  21.         This refcon can be used for maintaining state necessary for client's use
  22.         of the shape walking libraary.  It is reccomended that the client use a pointer to a
  23.         structure that at least contains and maintains the current point.  This current point
  24.         would get updated in each of the callbakds.
  25.         
  26.         The return value from the callbacks is a boolean indicating whether or not to stop early.
  27.         Returning false will result in the PathWalker routine to continue traversing.  returning
  28.         true will cause termination early.
  29.  
  30.             
  31.  
  32. ***************************************************************/
  33.  
  34.  
  35. #include "Types.h"
  36. #include "GXTypes.h"
  37. #include "GXMath.h"
  38. #include "GXGraphics.h"
  39. #include "GXLayout.h"
  40. #include "GXExceptions.h"
  41.  
  42. #include "PathWalking.h"
  43.  
  44.  
  45.  
  46. /****************************
  47.     NEXTBIT, PREVBIT:
  48.     Used for tranversal of bit arrays.
  49.     
  50.     theBit:                Boolean, true if bit was set.
  51.     theLong:            pointer to the current longword in bit array.
  52.     theMask:            current long word mask.  Initialize to 0x80000000 for first bit in array.
  53.     
  54.     NEXTBIT Checks current bit and then advances mask
  55.     PREVBIT rolls back mask and then checks bit.
  56.     
  57. *****************************/
  58. #define NEXTBIT(theBit, theLong, theMask)  {\
  59.                                                                                             theBit = ((*theLong & theMask) != 0); \
  60.                                                                                              if (!(theMask>>=1)) \
  61.                                                                                                 {theMask = 0x80000000; ++theLong;} \
  62.                                                                                         }
  63.  
  64. #define PREVBIT(theBit, theLong, theMask) {\
  65.                                                                                         if (!(theMask<<1)) \
  66.                                                                                             {theMask = 0x00000001; --theLong;} \
  67.                                                                                         theBit = ((*theLong & theMask) != 0); \
  68.                                                                                     }
  69.  
  70.  
  71.  
  72. /****************************************
  73.     Macro to interpolate between two points.
  74.     
  75.     p:            The point that will get the result.
  76.     p1:            The first point to interpolate between
  77.     p2:            The second point to interpolate between
  78.     
  79. *****************************************/
  80.     
  81. // Code to average two fixed point numbers.  Taken from GX file "paths.h"  Does math in 33 bits.
  82. static long Average(register long x, register long y) 
  83.     { 
  84.         return (x >> 1) + (y >> 1) + ((x & y) & 1);
  85.     }
  86.  
  87.  
  88. /* Macro to interpolate the point p which will be centered between p1 and p2 */
  89.  
  90. #define INTERPPOINT(p, p1, p2) {\
  91.                                                                     (p).x = Average( (p1).x, (p2).x) ; \
  92.                                                                     (p).y = Average( (p1).y, (p2).y) ; \
  93.                                                              }
  94.                                                                 
  95.  
  96.  
  97.  
  98. /***********************************
  99.     PathWalker:
  100.     
  101.     Walk a path shape, call back with each segment.
  102.     The points sent through the callbacks will include
  103.     any implicit points in the path determined by consecutive
  104.     off curve points.
  105.     
  106.     theShape:                    the path shape to walk.
  107.     DoMoveto:                    call back function for setting current point.
  108.     DoLineto:                    call back function for a line segment.
  109.     DoCurveto:                call back function for a curve segment.
  110.     DoClosepath:            call back function for closing the path.
  111.     refcon:                        this will get passed to your callbacks.
  112.     
  113. *************************************/
  114. Boolean PathWalker(gxShape theShape, TpwMovetoProc DoMoveto, TpwLinetoProc DoLineto, TpwCurvetoProc DoCurveto, TpwClosepathProc DoClosepath, void* refcon);
  115. Boolean PathWalker(gxShape theShape, TpwMovetoProc DoMoveto, TpwLinetoProc DoLineto, TpwCurvetoProc DoCurveto, TpwClosepathProc DoClosepath, void* refcon)
  116.     {
  117.         Boolean                                                status;
  118.         Ptr                                                        inPath;                            // We must walk through the Paths structure
  119.         gxShapeAttribute                            theAttributes;
  120.         long                                                    i, pointIndex;
  121.         long                                                    size;
  122.         long                                                    firstIndex, lastIndex;    // Index of first and last point ON curve.
  123.         Boolean                                                closeIt;                                // Is it open or closed.
  124.         long                                                    nContours;                            // Number of contours.
  125.         long                                                    nPoints;                                // Number of points in contour.
  126.         gxPoint*                                            pPoint;                                    // Point to a point.
  127.         gxPoint                                                firstPoint;                            // First point in the contour.
  128.         gxPoint                                                lastPoint;                            // The last point we output.
  129.         register unsigned long*                controlBitLong;                    // Pointer to control bits.
  130.         register unsigned long                cBitMask;                                // Mask for reading control bits.
  131.         unsigned long                                    lastBitMask;                        // Mask for last point in contour.
  132.         long                                                    cBitSize;                                // Number of longs for control bits.
  133.         gxPoint                                                q[3];                                        // Quadratic control points.
  134.         short                                                    qIndex;                                    // Indicates #points in curve segment so far.
  135.         Boolean                                                isOff;                                    // On the curve or off the curve.
  136.         Boolean                                                firstIsOn, lastIsOn;
  137.                 
  138.         /* If it is closedFrameFill we must close each contour */
  139.  
  140.         closeIt = (GXGetShapeFill(theShape) == gxClosedFrameFill);
  141.         
  142.         /***********
  143.             Make sure we have access to the shape data structure,
  144.             and then get it
  145.         ***********/        
  146.         theAttributes = GXGetShapeAttributes(theShape);
  147.         GXSetShapeAttributes(theShape, theAttributes | gxDirectShape);
  148.         
  149.         GXLockShape(theShape);
  150.         
  151.         inPath = (Ptr)GXGetShapeStructure(theShape, &size);            //Get a pointer to the structure.
  152.         check(inPath);
  153.                 
  154.         nContours = ((gxPaths*)inPath)->contours;                            //Get the number of countours.
  155.         inPath += sizeof(long);                                                                //Move pointer past contours field.
  156.                 
  157.         status = GXGetGraphicsError(nil);
  158.         nrequire(status, failed_KeepDirect);
  159.         
  160.         /** Now output all of the contours, break up to fit on stack if necessary **/
  161.                         
  162.         for (i = 0; i < nContours; i++) {        // Output the contours.
  163.         
  164.             nPoints = *(long*)inPath;                                            // Get the number of points for this contour.
  165.             inPath += sizeof(long);                                                // Move to the data.
  166.                         
  167.             if (nPoints > 0) {
  168.             
  169.                 controlBitLong = (unsigned long*)inPath;            // Get to the control bits.
  170.                 
  171.                 cBitSize = (nPoints + 31) / 32;                                // Compute the size of control bits in longs.
  172.                                     
  173.                 inPath += cBitSize * sizeof(long);                        // Skip past control bits, inPath now points to first point.
  174.                 
  175.                 pPoint = (gxPoint*)inPath;                                        // Get the first point in contour, leave inPath pointing here.
  176.                 
  177.                 cBitMask = 0x80000000U;                                                // Initilize the mask for reading bits.
  178.                 
  179.                 lastBitMask = 0x80000000U >> ((nPoints-1) & 0x0000001F);                            // Mod 32
  180.                 
  181.                 
  182.                 /** Compute the first and last point on the curve **/
  183.                 
  184.                 firstIsOn =  ((*controlBitLong & cBitMask) == 0);
  185.                 lastIsOn = ( ( *(controlBitLong + cBitSize - 1) & lastBitMask) == 0);
  186.                 
  187.                 if (firstIsOn && lastIsOn) {    // They both are on.
  188.                 
  189.                     firstPoint = *pPoint;
  190.                     firstIndex = 0;
  191.                     lastPoint = *(pPoint + nPoints - 1);
  192.                     lastIndex = nPoints;
  193.                     NEXTBIT(isOff, controlBitLong, cBitMask);            // Read bit for 1st point, set up for next.
  194.                     ++pPoint;
  195.                     
  196.                 } else if (firstIsOn) {                // first was on, last was off
  197.                     
  198.                     firstPoint = *pPoint;
  199.                     firstIndex = 0;
  200.                     
  201.                     lastPoint = firstPoint;
  202.                     
  203.                     lastIndex = nPoints + 1;
  204.                     NEXTBIT(isOff, controlBitLong, cBitMask);            // Read bit for 1st point, set up for next.
  205.                     ++pPoint;
  206.                 
  207.                 } else if (lastIsOn) {                // last was on, first is off
  208.                 
  209.                     register gxPoint* pLastPoint = pPoint + nPoints - 1;
  210.                     
  211.                     lastPoint = *pLastPoint;
  212.                     firstPoint = lastPoint;
  213.                     lastIndex = nPoints;
  214.                     
  215.                     firstIndex = -1;
  216.                 
  217.                 } else {                                            // they were both off
  218.                 
  219.                     register gxPoint* pLastPoint = pPoint + nPoints - 1;
  220.                     
  221.                     firstIndex = -1;
  222.                     lastIndex = nPoints + 1;
  223.                     
  224.                     INTERPPOINT(lastPoint, *pPoint, *pLastPoint);
  225.                     
  226.                     firstPoint = lastPoint;
  227.                                 
  228.                 } //end if
  229.                 
  230.                 
  231.                 /*** Output the contour ****/
  232.                 
  233.                 q[0] = firstPoint;
  234.                 qIndex = 0;
  235.                 status = (*DoMoveto)(&(q[0]), refcon);
  236.                 nrequire(status, failed_Output);
  237.                     
  238.                 // Loop over all points but the first and last ON the curve.
  239.                 
  240.                 NEXTBIT(isOff, controlBitLong, cBitMask);        // Check the first point in the looping.
  241.                 pointIndex = firstIndex + 1;
  242.                 while (pointIndex < (lastIndex - 1)) {            // I know, should cache lastPointIndex-1
  243.                                     
  244.                     if (!isOff) {                                    // If the next point is on the curve:
  245.                     
  246.                         if ( qIndex == 0) {                    // If we have only q0, then do a line and start over.
  247.                     
  248.                             status = (*DoLineto)(pPoint, refcon);
  249.                             nrequire(status, failed_Output);
  250.                             q[0] = *pPoint++;
  251.                             ++pointIndex;
  252.     
  253.                             NEXTBIT(isOff, controlBitLong, cBitMask);
  254.                                                         
  255.                         } else {                                        // We must have q0 and q1, do a curve: q0, q1, q2
  256.                         
  257.                             q[2] = *pPoint++;
  258.                             status = (*DoCurveto)(q, refcon);
  259.                             nrequire(status, failed_Output);
  260.                             q[0] = q[2];
  261.                             qIndex = 0;
  262.                             ++pointIndex;
  263.                             NEXTBIT(isOff, controlBitLong, cBitMask);
  264.                                                     
  265.                         }//end if
  266.                     
  267.                     } else {
  268.                     
  269.                         if (qIndex == 0) {                    // If we only have one point so far, this becomes 2nd.
  270.                         
  271.                             q[1] = *pPoint++;
  272.                             qIndex = 1;
  273.                             NEXTBIT(isOff, controlBitLong, cBitMask);
  274.                             ++pointIndex;
  275.                         
  276.                         } else {                                        // We had 2 points, interpolate to get 3rd and do a curve
  277.                         
  278.                             INTERPPOINT(q[2], q[1], *pPoint);
  279.                             
  280.                             status = (*DoCurveto)( q, refcon);
  281.                             nrequire(status, failed_Output);
  282.                             qIndex = 0;
  283.                             q[0] = q[2];                    
  284.  
  285.                         }//end if
  286.                     
  287.                     }//end if
  288.                 
  289.  
  290.                 }//end while
  291.                                 
  292.                 /** Now handle the last point that is ON the curve in the contour **/
  293.                 
  294.                 if (qIndex == 0) {                // If we only had one point so far, Do a line.
  295.                                     
  296.                     status = (*DoLineto)( &lastPoint, refcon);
  297.                     nrequire(status, failed_Output);        
  298.                                     
  299.                 } else {                                    // Else, we must have had 2 points so far, Do a curve.
  300.                 
  301.                     q[2] = lastPoint;
  302.                     status = (*DoCurveto)(q, refcon);
  303.                     nrequire(status, failed_Output);
  304.                                     
  305.                 }//end if
  306.                 
  307.                 if (closeIt) {
  308.                 
  309.                     status = (*DoClosepath)(refcon);
  310.                     nrequire(status, failed_Output);
  311.                     
  312.                 }//end if
  313.                 
  314.                 /** Point into the next contour - inPath was pointing to first point in contour **/
  315.                 
  316.                 inPath += nPoints * sizeof(gxPoint);
  317.                                     
  318.             }//end if
  319.         
  320.         }//endo for i
  321.         
  322. failed_Output:
  323.  
  324.         /** Restore things, though the shape is a copy and we really don't have to. **/
  325.  
  326.         GXSetShapeAttributes(theShape, theAttributes);
  327.         GXUnlockShape(theShape);
  328.         
  329. failed_KeepDirect:        
  330.         
  331.  
  332.         return(status);
  333.     
  334.     }//PathWalker
  335.     
  336.  
  337.  
  338.  
  339. /***********************************
  340.     PolygonWalker:
  341.     
  342.     Walk a polygon and call back
  343.     
  344. *************************************/
  345. OSErr PolygonWalker(gxShape theShape, TpwMovetoProc DoMoveto, TpwLinetoProc DoLineto, TpwClosepathProc DoClosepath, void* refcon);
  346. OSErr PolygonWalker(gxShape theShape, TpwMovetoProc DoMoveto, TpwLinetoProc DoLineto, TpwClosepathProc DoClosepath, void* refcon)
  347.     {
  348.         Boolean                            status = false;
  349.         Ptr                                    inPolygon;                            // We must walk through the polygons structure
  350.         gxShapeAttribute        theAttributes;
  351.         long                                i, j;
  352.         Boolean                            closeIt;                                // Is it open or closed.
  353.         long                                nContours;                            // Number of contours.
  354.         long                                nPoints;                                // Number of points in contour.
  355.         gxPoint*                        pPoint;                                    // Point to a point.
  356.         long                                size;
  357.                 
  358.         
  359.         /* If it is closedFrameFill we must close each contour */
  360.  
  361.         closeIt = (GXGetShapeFill(theShape) == gxClosedFrameFill);
  362.         
  363.         /***********
  364.             Make sure we have access to the shape data structure,
  365.             and then get it
  366.         ***********/        
  367.         theAttributes = GXGetShapeAttributes(theShape);
  368.         GXSetShapeAttributes(theShape, theAttributes | gxDirectShape);
  369.         GXLockShape(theShape);
  370.         
  371.         status = GXGetGraphicsError(nil);
  372.         nrequire(status, failed_KeepDirect);
  373.         
  374.         
  375.         inPolygon = (Ptr)GXGetShapeStructure(theShape, &size);            //Get a pointer to the structure.
  376.         check(inPolygon);
  377.         
  378.         nContours = ((gxPolygons*)inPolygon)->contours;                            //Get the number of countours.
  379.  
  380.         inPolygon += sizeof(long);                                                                    //Move pointer past contours field.
  381.                 
  382.         /** Now output all of the contours **/
  383.                 
  384.         for (i = 0; i < nContours; i++) {        // Output the contours.
  385.         
  386.             nPoints = *(long*)inPolygon;                                        // Get the number of points for this contour.
  387.             
  388.             inPolygon += sizeof(long);                                            // Move to the data.
  389.             
  390.             if (nPoints > 0) {
  391.             
  392.                 pPoint = (gxPoint*)inPolygon;                                        // Get the first point in contour.
  393.                 inPolygon += sizeof(gxPoint);                                        // Move past it.
  394.                 
  395.                 status = (*DoMoveto)( pPoint, refcon);                    // Do the moveto
  396.                 nrequire(status, failed_Output);
  397.                                                             
  398.                 for (j = 1; j < nPoints; j++) {                                    // Output the points for the countour.
  399.                             
  400.                     pPoint = (gxPoint*)inPolygon;                                    //        Get the next point.
  401.                     inPolygon += sizeof(gxPoint);
  402.                                     
  403.                     status = (*DoLineto)( pPoint, refcon);            //        Add a line to the PS path.
  404.                     nrequire(status, failed_Output);
  405.                                                         
  406.                 }//end for j
  407.                 
  408.                 if (closeIt) {
  409.                 
  410.                     status = (*DoClosepath)(refcon);
  411.                     nrequire(status, failed_Output);
  412.                     
  413.                 }//end if
  414.                 
  415.             }//end for
  416.         
  417.         }//endo for i
  418.         
  419.  
  420. failed_Output:
  421.         /** Restore the shape to the way we got it. **/
  422.         
  423.         GXSetShapeAttributes(theShape, theAttributes);
  424.         GXUnlockShape(theShape);
  425.  
  426. failed_KeepDirect:        
  427.         
  428.         return(status);
  429.     
  430.     }//PolygonWalker
  431.  
  432.  
  433.  
  434. /**************************************
  435.  
  436.  
  437.     ShapeWalker:
  438.     
  439.          Main entry point for path/polygon traversal.
  440.  
  441.         return result:
  442.             true if shape walking terminated before completion of entire shape, by one of the callbacks.
  443.  
  444. **************************************/
  445. Boolean  ShapeWalker(gxShape theShape,     TpwMovetoProc DoMoveto, TpwLinetoProc DoLineto, TpwCurvetoProc DoCurveto, TpwClosepathProc DoClosepath,    void* refcon)
  446.     {
  447.         Boolean             result = true;
  448.         gxShapeType        theType = GXGetShapeType(theShape);
  449.         gxCurve                theCurve;
  450.         gxLine                theLine;
  451.         gxRectangle        theRectangle;
  452.         gxPoint                thePoint;
  453.     
  454.         switch(theType) {
  455.  
  456.             /* paths and polygons require above routines for walking */
  457.             case gxPathType:
  458.                 result = PathWalker(theShape, DoMoveto, DoLineto, DoCurveto, DoClosepath, refcon);
  459.                 break;
  460.             
  461.             case gxPolygonType:
  462.                 result = PolygonWalker(theShape, DoMoveto, DoLineto, DoClosepath, refcon);
  463.                 break;
  464.                 
  465.             /* other shape types can easily be handled here by calling callbacks with the data */
  466.             case gxCurveType:
  467.                 GXGetCurve(theShape, &theCurve);
  468.                 result = DoMoveto(&theCurve.first, refcon);
  469.                 if (!result) {
  470.                     gxPoint        *pts = (gxPoint*)&theCurve;                // a curve is the same as an array of three points.
  471.                     result = DoCurveto(pts, refcon);
  472.                 }//end if
  473.                 break;
  474.  
  475.             case gxLineType:
  476.                 GXGetLine(theShape, &theLine);
  477.                 result = DoMoveto(&theLine.first, refcon);
  478.                 if (!result)
  479.                     result = DoLineto(&theLine.last, refcon);
  480.                 break;
  481.                 
  482.             case gxRectangleType:
  483.                 /* rectangles are a little more work */
  484.                 GXGetRectangle(theShape, &theRectangle);
  485.                 thePoint.x = theRectangle.left; thePoint.y = theRectangle.top;
  486.                 result = DoMoveto(&thePoint, refcon);                // (left, top);
  487.                 if (!result) {
  488.                     thePoint.x = theRectangle.right;                    // (right, top);
  489.                     result = DoLineto(&thePoint, refcon);
  490.                     if (!result) {
  491.                         thePoint.y = theRectangle.bottom;                // (right, bottom);
  492.                         result = DoLineto(&thePoint, refcon);
  493.                         if (!result) {
  494.                             thePoint.x = theRectangle.left;                // (left, bottom);
  495.                             result = DoLineto(&thePoint, refcon);
  496.                             if (!result) {
  497.                                 result = DoClosepath(refcon);                // close it.
  498.                             }//end if
  499.                         }//end if
  500.                     }//end if
  501.                 }//end if
  502.                 
  503.             /* other shape types not allowed */
  504.             default:
  505.                 GXPostGraphicsError(illegal_type_for_shape);
  506.                 break;
  507.         
  508.         }//end switch
  509.             
  510.         return(result);
  511.         
  512.     }//ShapeWalker
  513.  
  514.  
  515.